
// 39.组合总和
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& nums, int target) {
        // 使用DFS来实现
        int n = nums.size();
        sort(nums.begin() , nums.end());
        vector<vector<int>> ret;
        vector<int> tmp;
        function<void(int , int )> dfs = [&](int pos , int leave )
        {
            if(leave == 0)
            {
                ret.push_back(tmp);
                return ;
            }
            if(pos == n || nums[pos] > leave) return ;
            // 不选
            dfs(pos + 1 , leave);
            tmp.push_back(nums[pos]);
            // 选一个,下一次依旧是从pos位置开始选,还可以再选pos位置
            dfs(pos , leave - nums[pos]);
            tmp.pop_back();
        };
        dfs(0 , target);
        return ret;
    }
};